/**
  @(#)$Id: AL_ListSeq.h 73 2013-10-10 12:38:11Z xiaoting $
  @brief     Sequence table is in the computer memory as an array stored linear form, refers to a group of contiguous memory cells 
  storing data elements sequentially linear structure. Linear form using sequential storage mode it is called the order form. Sequence 
  table is the table node sequentially stored in the computer memory a set of contiguous memory cell.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
							         
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-10 20:38:11 +0800 (周四, 10 十月 2013) $
  @Revision $Revision: 73 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_ListSeq.h 73 2013-10-10 12:38:11Z xiaoting $
 */

#ifndef CXX_AL_LISTSEQ_H
#define CXX_AL_LISTSEQ_H

///////////////////////////////////////////////////////////////////////////
//			AL_ListSeq
///////////////////////////////////////////////////////////////////////////

template<typename T> 
class AL_ListSeq
{
public:
	static const DWORD LISTSEQ_DEFAULTSIZE			= 100;
	static const DWORD LISTSEQ_MAXSIZE				= 0xffffffff;
	static const DWORD LISTSEQ_POSITION_INVALID		= 0xffffffff;
	/**
	* Construction
	*
	* @param DWORD dwSize (default value: LISTSEQ_DEFAULTSIZE)
	* @return
	* @note
	* @attention
	*/
	AL_ListSeq(DWORD dwSize = LISTSEQ_DEFAULTSIZE);

	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention
	*/
	~AL_ListSeq();

	/**
	* Length
	*
	* @param VOID
	* @return DWORD
	* @note get the length of the list
	* @attention
	*/
	DWORD Length() const;
	
	/**
	* Find
	*
	* @param const T& tData <IN> 
	* @return DWORD
	* @note find the position of tData 
	* @attention if not find, will be return 0xffffffff
	*/
	DWORD Find(const T& tData) const;

	/**
	* IsElement
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note the tData  is in the list?
	* @attention
	*/
	BOOL IsElement(const T& tData) const;

	/**
	* Insert
	*
	* @param DWORD dwIndex <IN>
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL Insert(DWORD dwIndex,const T& tData);

	/**
	* InsertBegin
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertBegin(const T& tData);


	/**
	* InsertEnd
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note inset the tData  into the list at the position
	* @attention
	*/
	BOOL InsertEnd(const T& tData);

	/**
	* Remove
	*
	* @param const T& tData <IN> 
	* @return BOOL
	* @note remove the tData in the list
	* @attention
	*/
	BOOL Remove(const T& tData);

	/**
	* RemoveAt
	*
	* @DWORD dwIndex <IN> 
	* @return BOOL
	* @note remove the tData in the list at the index (dwIndex)
	* @attention
	*/
	BOOL RemoveAt(DWORD dwIndex);

	/**
	* IsEmpty
	*
	* @param VOID
	* @return BOOL
	* @note the list has data?
	* @attention
	*/
	BOOL IsEmpty() const;

	/**
	* Get
	*
	* @param	DWORD dwIndex <IN>
	* @param	T& tTypeOut <OUT>
	* @return BOOL
	* @note get the const T& at the position
	* @attention  the dwIndex must is little than the list length
	*/
	BOOL Get(DWORD dwIndex, T& tTypeOut) const;

	/**
	* Set
	*
	* @param	DWORD dwIndex <IN>
	* @param	const T& tData <IN>
	* @param	T& tTypeOut <OUT>
	* @return BOOL
	* @note Replaced with the element element element on position index, and returns the old element...
	* @attention Index must in the list
	*/
	BOOL Set(DWORD dwIndex, const T& tData, T& tTypeOut);

	/**
	* Clear
	*
	* @param VOID
	* @return VOID
	* @note clear the data in the list
	* @attention all data will be clear
	*/
	VOID Clear();

	/**
	*Assignment
	*
	* @param const AL_ListSeq<T>& cAL_ListSeq
	* @return AL_ListSeq<T>&
	*/
	AL_ListSeq<T>& operator = (const AL_ListSeq<T>& cAL_ListSeq);

protected:
private:
	/**
	* GetBuffer
	*
	* @param VOID
	* @return VOID
	* @note get the work buffer
	* @attention when the buffer is not enough, it will become to double
	*/
	VOID GetBuffer();
	
	/**
	* IsFull
	*
	* @param VOID
	* @return BOOL
	* @note the buffer is full?
	* @attention
	*/
	BOOL IsFull() const;

	/**
	*Copy Construct
	*
	* @param const AL_ListSeq<T>& cAL_ListSeq
	* @return
	*/
	AL_ListSeq(const AL_ListSeq<T>& cAL_ListSeq);

public:
protected:
private: 
	
	T*			m_pElements;
	DWORD		m_dwMaxSize;
	DWORD		m_dwSize;
};

///////////////////////////////////////////////////////////////////////////
//			AL_ListSeq
///////////////////////////////////////////////////////////////////////////
/**
* Construction
*
* @param DWORD dwSize (default value: LISTSEQ_DEFAULTSIZE)
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListSeq<T>::AL_ListSeq(DWORD dwSize):
m_pElements(NULL),
m_dwMaxSize(dwSize),
m_dwSize(0x00)
{
	if (0x00 == m_dwMaxSize) {
		//for memory deal
		m_dwMaxSize = 1;
	}
	GetBuffer();
}

/**
* Destruction
*
* @param
* @return
* @note
* @attention
*/
template<typename T> 
AL_ListSeq<T>::~AL_ListSeq()
{
	if (NULL != m_pElements) {
		delete[] m_pElements;
		m_pElements = NULL;
	}
}

/**
* Length
*
* @param
* @return
* @note get the length of the list
* @attention
*/
template<typename T> DWORD 
AL_ListSeq<T>::Length() const
{
	if (TRUE == IsEmpty()) {
		return 0;
	}

	return m_dwSize;
}

/**
* Find
*
* @param const T& tData <IN> 
* @return DWORD
* @note find the position of tData 
* @attention  if not find, will be return 0xffffffff
*/
template<typename T> DWORD 
AL_ListSeq<T>::Find(const T& tData) const
{
	if (TRUE == IsEmpty()) {
		return LISTSEQ_POSITION_INVALID;
	}

	for(DWORD dwCnt=0x00; dwCnt<Length();dwCnt++) {
		if (m_pElements[dwCnt] == tData ) {
			return dwCnt;
		}
	}
	return LISTSEQ_POSITION_INVALID;
}

/**
* IsElement
*
* @param const T& tData <IN> 
* @return BOOL
* @note the tData  is in the list?
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::IsElement(const T& tData) const
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}

	if (LISTSEQ_POSITION_INVALID == Find(tData )) {
		return FALSE;
	}

	return TRUE;
}

/**
* Insert
*
* @param DWORD dwIndex <IN>
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::Insert(DWORD dwIndex, const T& tData)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}
	if (TRUE == IsFull()) {
		// full, need to get more work buffer
		GetBuffer();
	}
	
	for(DWORD dwCnt=(Length()-1+1); dwCnt>dwIndex; dwCnt--) {
		m_pElements[dwCnt] = m_pElements[dwCnt-1];
	}
	m_pElements[dwIndex] = tData ;

	m_dwSize++;
	return TRUE;
}

/**
* InsertBegin
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::InsertBegin(const T& tData)
{
	return Insert(0, tData);
}

/**
* InsertEnd
*
* @param const T& tData <IN> 
* @return BOOL
* @note inset the tData  into the list at the position
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::InsertEnd(const T& tData)
{
	return Insert(Length(), tData);
}


/**
* Remove
*
* @param const T& tData <IN> 
* @return BOOL
* @note remove the tData in the list
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::Remove(const T& tData)
{
	if (TRUE == IsEmpty()) {
		return FALSE;
	}
	
	BOOL bRemove = FALSE;
	for(DWORD dwCnt=0x00; dwCnt<Length();dwCnt++) {
		if (m_pElements[dwCnt] == tData ) {
			bRemove = RemoveAt(dwCnt);
			if (FALSE == bRemove) {
				return bRemove;
			}
		}
	}
	return bRemove;
}

/**
* RemoveAt
*
* @param DWORD dwIndex <IN> 
* @return BOOL
* @note remove the tData in the list at the index (dwIndex)
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::RemoveAt(DWORD dwIndex)
{
	if (dwIndex > Length()) {
		//can not insert to this position
		return FALSE;
	}

	for(DWORD dwCnt=dwIndex; dwCnt<Length()-1; dwCnt++) {
		m_pElements[dwCnt] = m_pElements[dwCnt+1];
	}
	m_dwSize--;
	return TRUE;
}

/**
* IsEmpty
*
* @param
* @return BOOL
* @note the list has data?
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::IsEmpty() const
{
	return (0x00 == m_dwSize) ? TRUE:FALSE;
}

/**
* Get
*
* @param	DWORD dwIndex <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note get the T at the position
* @attention the dwIndex must is little than the list length
*/
template<typename T> BOOL
AL_ListSeq<T>::Get(DWORD dwIndex, T& tTypeOut) const
{
	if (TRUE == IsEmpty()) {
		//error
		return FALSE;
	}

	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}

	tTypeOut = m_pElements[dwIndex];
	return TRUE;
}

/**
* Set
*
* @param	DWORD dwIndex <IN>
* @param	const T& tData <IN>
* @param	T& tTypeOut <OUT>
* @return BOOL
* @note Replaced with the element element element on position index, and returns the old element...
* @attention Index must in the list
*/
template<typename T> BOOL 
AL_ListSeq<T>::Set(DWORD dwIndex, const T& tData, T& tTypeOut)
{
	if (Length()-1 < dwIndex) {
		//error
		return FALSE;
	}

	tTypeOut = m_pElements[dwIndex];
	m_pElements[dwIndex] = tData ;
	return TRUE;
}

/**
* Clear
*
* @param VOID
* @return VOID
* @note clear the data in the list
* @attention all data will be clear
*/
template<typename T> VOID 
AL_ListSeq<T>::Clear()
{
	//memset(m_pElements, 0x00, sizeof(T)*Length());		//can not use memset, as to pointer or virtural pointer of class
	m_dwSize = 0x00;
}

/**
* GetBuffer
*
* @param VOID
* @return VOID
* @note get the work buffer
* @attention when the buffer is not enough, it will become to double
*/
template<typename T> VOID 
AL_ListSeq<T>::GetBuffer()
{

	if ( (FALSE == IsFull()) && (NULL != m_pElements) ) {
		//we do not need to get more buffer
		return;
	}

	if (NULL == m_pElements) {
		if(0 < m_dwMaxSize){
			//get the new work buffer
			m_pElements = new T[m_dwMaxSize];
			//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
		}
		return;
	}

	//we need to get more buffer, store the previous pointer
	T* pLastTpye = NULL;

	// it will become to double
	pLastTpye = m_pElements;
	if (LISTSEQ_MAXSIZE == m_dwMaxSize) {
		//can not get more buffer, please check the application
		return;
	}
	else if (LISTSEQ_MAXSIZE/2 < m_dwMaxSize) {
		m_dwMaxSize = LISTSEQ_MAXSIZE;
	}
	else {
		m_dwMaxSize *= 2;
	}
	if(0 < m_dwMaxSize){
		//get the new work buffer
		m_pElements = new T[m_dwMaxSize];
		//memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);		//can not use memset, as to pointer or virtural pointer of class
	}
	//need to copy the last to the current
	for (DWORD dwCpy=0x00; dwCpy<Length(); dwCpy++) {
		m_pElements[dwCpy] = pLastTpye[dwCpy];
	}
//	memcpy(m_pElements, pLastTpye, sizeof(T)*Length());				//can not use memcopy, as to pointer
	
	//free the last work buffer
	delete[] pLastTpye;
	pLastTpye = NULL;
}

/**
* IsFull
*
* @param
* @return BOOL
* @note the buffer is full?
* @attention
*/
template<typename T> BOOL 
AL_ListSeq<T>::IsFull() const
{
	return (m_dwMaxSize <= Length()) ? TRUE:FALSE;
}

/**
*Assignment
*
* @param const AL_ListSeq<T>& cAL_ListSeq
* @return AL_ListSeq<T>&
*/
template<typename T> AL_ListSeq<T>& 
AL_ListSeq<T>::operator = (const AL_ListSeq<T>& cAL_ListSeq)
{
	Clear();
	T tData;
	for (DWORD dwAssign=0x00; dwAssign<cAL_ListSeq.Length(); dwAssign++) {
		if (TRUE == cAL_ListSeq.Get(dwAssign, tData)) {
			InsertEnd(tData);
		}
	}
	return *this;
}
#endif // CXX_AL_LISTSEQ_H
/* EOF */
